package com.hqq.exercise.list;

import java.util.Stack;

/**
 * FirstCommonNode 两个链表的第一个公共结点
 * 题目描述:
 * 输入两个链表，找出它们的第一个公共结点
 * 思路:
 * 1.使用栈保存两个链表的节点,遍历栈找到最后一个相等的节点
 * 2.先遍历一遍得到两个链表的长度 较长的链表先遍历n个节点 之后两个链表同步遍历 直到找到第一个相等的节点
 * Created by heqianqian on 2017/8/22.
 */
public class FirstCommonNode {

    /**
     * 使用栈保存两个链表的节点,遍历栈找到最后一个相等的节点
     */
    public static ListNode findFirstCommonNodeByStack(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        /*两个辅助栈*/
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();

        /*节点入栈*/
        pushNode(node1, stack1);
        pushNode(node2, stack2);

        ListNode n1 = stack1.pop();
        ListNode temp = n1;

        /*找到最后一个相等的节点*/
        while (!stack1.empty() && !stack2.empty() && n1.equals(stack2.pop())) {
            temp = n1;
            n1 = stack1.pop();
        }
        return temp;
    }

    /**
     * 先遍历一遍得到两个链表的长度 较长的链表先遍历n个节点 之后两个链表同步遍历 直到找到第一个相等的节点
     */
    public static ListNode findFirstCommonNodeOptimized(ListNode node1, ListNode node2) {

        if (node1 == null || node2 == null) {
            return null;
        }

        /*分別计算两个链表的长度*/
        int length1 = calLength(node1);
        int length2 = calLength(node2);

        /*长度大的链表先遍历|length1-length2|个长度*/
        if (length1 > length2) {
            for (int i = 0; i < length1 - length2; i++) {
                node1 = node1.next;
            }
        } else {
            for (int i = 0; i < length2 - length1; i++) {
                node2 = node2.next;
            }
        }

        /*同步遍历 找到第一个相等的节点*/
        while (node1 != null && node2 != null) {
            if (node1.equals(node2)) {
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }

        return null;
    }

    /**
     * 计算链表的长度
     */
    private static int calLength(ListNode node1) {
        int length = 0;
        while (node1 != null) {
            length++;
            node1 = node1.next;
        }
        return length;
    }


    /**
     * 链表节点入栈
     */
    private static void pushNode(ListNode node1, Stack<ListNode> stack1) {
        while (node1 != null) {
            stack1.push(node1);
            node1 = node1.next;
        }
    }
}
